package Leetcode.lc438;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/***
 * 438找到所有给定字符串的异位词
 * 给定两个字符串 s 和 p，找到 s 中所有 p 的 异位词 的子串，返回这些子串的起始索引。不考虑答案输出的顺序。
 */

public class Sloution {
    public List<Integer> findAnagrams(String s, String p) {
        /***
         * 使用灵神的定长滑动窗口
         */
        char[] pattern = new char[26];
        char[] chars = new char[26];
        List<Integer> res = new ArrayList<>();
        //模式串匹配数组
        for(int i=0;i<p.length();i++){
            pattern[p.charAt(i)-'a']++;
        }
        for(int right=0;right<s.length();right++){
            chars[s.charAt(right)-'a']++;
            int left=right+1-p.length();
            if(left<0) continue;
            if(Arrays.equals(pattern,chars)){
                res.add(left);
            }
            chars[s.charAt(left)-'a']--;
        }
        return res;
    }

    public static void main(String[] args) {
        Sloution sloution = new Sloution();
        String a="acbdbdbd";
        String b="bd";
        List<Integer> anagrams = sloution.findAnagrams(a, b);

    }

}
